#include <stdlib.h>
#include "heap.h"


//Initialisation d'un tas
//-----------------------------------------------------------------------------
void heap_init(heap_t * h, int maxsize)
//-----------------------------------------------------------------------------
{
	h->data 	= calloc(maxsize,sizeof(void *));
	h->val		= calloc(maxsize,sizeof(int));
	h->maxsize	= maxsize;
	h->size		= 0;
}


//destruction d'un tas (libère la mémoire)
//-----------------------------------------------------------------------------
void heap_free(heap_t * h)
//-----------------------------------------------------------------------------
{
	free(h->data);
	free(h->val);
	h->maxsize	= 0;
	h->size		= 0;
}


//insertion d'un élément dans le tas => retourne 0 si tas plein sinon le nombre d'éléments
//-----------------------------------------------------------------------------
int heap_push(heap_t * heap, int val ,void * data)
//-----------------------------------------------------------------------------
{
	int i=heap->size;
	int up,swval;
	void * swdata;


	if(heap->size >= heap->maxsize)	return 0;

	//insertion en fin de vecteur
	heap->size++;
	heap->val[i] =val;
	heap->data[i]=data;

	//Tamiser pour faire remonter le min O(log n)
	while(i>0)
	{
		up = (i%2)?i/2:(i/2)-1;
		if( heap->val[i]< heap->val[up] )
		{
			//échange (la donnée doit remonter en même temps que la valeur)
			swval =heap->val[i]; heap->val[i] =heap->val[up]; heap->val[up] =swval;
			swdata=heap->data[i];heap->data[i]=heap->data[up];heap->data[up]=swdata;

		}else{
			//sortie rapide
			break;
		}

		i=up;
	}

	return heap->size;
}


//extratction du minimum => retourne le nombre d'élément restant
//-----------------------------------------------------------------------------
int heap_pop(heap_t * heap)
//-----------------------------------------------------------------------------
{

	int i=heap->size-1;
	int min,l,r,swval;
	void * swdata;

	if(heap->size < 2){ (heap->size<1)? heap->size=0 : heap->size--;	return 0;}

	heap->size--;

	//Le premier sort et est remplacé par le dernier
	swval =heap->val[0]; heap->val[0] =heap->val[i]; heap->val[i] =swval;
	swdata=heap->data[0];heap->data[0]=heap->data[i];heap->data[i]=swdata;
	//rmq: Je conserve l'élément sortant en fin de vecteur ainsi lorsqu'on aura
	// extrait tous les min le vecteur sera trié par ordre décroissant (réutilisabilité !)

	i=0; l=1; r=2; // i=> noeud courrant l=> fils gauche de i r=> fils droit de i
	//Tamiser pour faire déscendre le sommet à la bonne place
	while( r < heap->size ) //tanque i a deux fils
	{
		min = ( heap->val[l] < heap->val[r] ) ? l:r;

		if( heap->val[i] < heap->val[min] ) break;

		//échanger
		swval =heap->val[min]; heap->val[min] =heap->val[i]; heap->val[i] =swval;
		swdata=heap->data[min];heap->data[min]=heap->data[i];heap->data[i]=swdata;

		i=min; l=(2*i)+1; r=(2*i)+2;
	}

	if( (l < heap->size) && (heap->val[i] > heap->val[l]) )
	//cas particulier ou i n'as qu'un fils gauche et doit descendre
	{
		//dernier échange
		swval =heap->val[l]; heap->val[l] =heap->val[i]; heap->val[i] =swval;
		swdata=heap->data[l];heap->data[l]=heap->data[i];heap->data[i]=swdata;
	}

	return heap->size;
}


//Renvois le sommet du tas (ie le minimum) ou NULL si vide
//-----------------------------------------------------------------------------
void * heap_getMin(heap_t * heap)
//-----------------------------------------------------------------------------
{
	return (heap->size > 0) ? heap->data[0]:NULL;
}

/*
#include <stdio.h>
//-----------------------------------------------------------------------------
int main()
//-----------------------------------------------------------------------------
{
	heap_t h;
	char lettre[9][7]={	{'t','r','o','i','s','\0',' '},
						{'c','i','n','q','\0',' ',' '},
						{'q','u','a','t','r','e','\0'},
						{'s','e','p','t','\0',' ',' '},
						{'s','i','x','\0',' ',' ',' '},
						{'u','n','\0',' ',' ',' ',' '},
						{'d','e','u','x','\0',' ',' '},
						{'h','u','i','t','\0',' ',' '},
						{'W','A','R','F','!','\0',' '}
					  };
	int val[9] = {3,5,4,7,6,1,2,8,329};
	int i;
	char * str;

	heap_init(&h,8);

	for(i=0; i<9; i++) printf("- %d\t%s\n",val[i],&lettre[i][0]);
	for(i=0; i<10; i++) heap_push(&h,val[i], (void *)&lettre[i][0] );
	for(i=0; i<10; i++)
	{
		str=(char *)heap_getMin(&h);
		heap_pop(&h);
		printf("%s ",str);
	}

	printf("\n");
	return 0;
}
*/

//
